import java.util.Arrays;

public class Solution473 {
    public boolean makesquare(int[] matchsticks) {
        if (Arrays.stream(matchsticks).sum()%4!=0){
            return false;
        }else{
            int target=Arrays.stream(matchsticks).sum()/4;
            Arrays.sort(matchsticks);
            if (matchsticks[matchsticks.length-1]>target){
                return false;
            }
            int[] f=new int[1<<matchsticks.length];
            return dfs(0,0,0,matchsticks,target,f);
        }
    }

    private boolean dfs(int nums, int now, int state, int[] matchsticks,int target,int[] f) {
        if (f[state]==0){
            if (now==3){
                f[state]=1;
            }else{
                for (int i=matchsticks.length-1;i>=0;i--){
                    if (nums+matchsticks[i]<=target  && (state&(1<<i))==0){
                        if (nums+matchsticks[i]==target){
                            if (dfs(0,now+1,state|(1<<i),matchsticks,target,f)){
                                f[state]=1;
                                break;
                            }
                        }else{
                            if (dfs(nums+matchsticks[i],now,state|(1<<i),matchsticks,target,f)){
                                f[state]=1;
                                break;
                            }
                        }
                    }
                }
            }
            if (f[state]==0){
                f[state]=-1;
            }
        }
        return f[state]==1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution473().makesquare(new int[]{1,1,2,2,2}));
    }
}
